#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>

using namespace std;

#define PRODUCTION_MAX 512
#define ITEM_MAX 128
#define VN_MAX 128
#define VT_MAX 128
#define STRING_MAX 1024

/**
 * used to index the sorted productions and items
 * @ptr:    means the subscript of production[] or item[]
 * @length: means the same type size
**/
struct Index
{
  int ptr;
  int size;
  Index (): ptr(-1), size(0) { }
};

struct Production
{
  int A;
  int B;
  int C;
};

struct Item
{
  int A;
  char B;
};

/**
 * deprecated
 * tree[i][j][k] = {x, y}
 * means in string[i][j] used kth in index to reduce to A(i or p)'s count is y
 * @root:   means
 * @num:    means
**/
struct Tree
{
  int root;
  unsigned num;

  Tree (): root(-1), num(-1) { }
  Tree (int root, unsigned num): root(root), num(num) { }
};

// index of Item by production.B and production.C
Index p_idx[VN_MAX][VN_MAX];

// index of Item by item.B
Index i_idx[VT_MAX];

Production production[PRODUCTION_MAX];

Item item[ITEM_MAX];

// tree[i][j][k] = {x, y}
// means in string[i][j] used kth in index to reduce to A(i or p)'s count is y
Tree tree[STRING_MAX][STRING_MAX][VN_MAX];

// record the number of times the (sub)string is reduced
// tree_num[i][j] = k (0 <= i <= j < len(string))
// means the number of times the string[i][j] reduced is k
int tree_num[STRING_MAX][STRING_MAX];

int vn_num;
int production_num;
int item_num;
int string_length;
char str[STRING_MAX];

int main(int argc, char **argv)
{
  // basic io
  if (argc != 2)
  { printf ("cyk <input.txt>"); return 0; }

  freopen(argv[1], "r", stdin);
  scanf("%d\n", &vn_num); scanf("%d\n", &production_num);
  for (int i = 0; i < production_num; i++)
    scanf("<%d>::=<%d><%d>\n", &production[i].A, &production[i].B, &production[i].C);
  scanf("%d\n", &item_num);
  for (int i = 0; i < item_num; i++)
    scanf("<%d>::=%c\n", &item[i].A, &item[i].B);
  scanf("%d\n", &string_length); scanf("%s\n", str);

  // sort ascending order by item.B and item.A
  sort (item, item + item_num, [](const Item& a,
                                  const Item& b)
  { return a.B == b.B ? a.A < b.A : a.B < b.B; });
#define __DEBUG__ 1
#ifdef __DEBUG__
  printf ("line: %d\n", __LINE__);
  for (int i = 0; i < item_num; i++) 
    printf ("%d -> %c\n", item[i].A, item[i].B);
  puts ("--------------------------------");
#endif

  // init the index which indexed by [item.B]
  for (int i = 0; i < item_num; i++)
  {
    int t = item[i].B;
    if (i_idx[t].ptr == -1)
      i_idx[t].ptr = i;
    i_idx[t].size++;
  }

#ifdef __DEBUG__
  printf ("line: %d\n", __LINE__);
  for (int i = 97; i < 99; i++)
    printf ("%c:\t%d %d\n", (char)i, i_idx[i].ptr, i_idx[i].size);
  puts ("--------------------------------");
#endif

  // sort ascending order by production.B, production.C and production.A
  sort (production, production + production_num, [](const Production& a,
                                                    const Production& b)
  { return a.B == b.B ? (a.C == b.C ? a.A < b.A : a.C < b.C) : a.B < b.B; });

#ifdef __DEBUG__
  printf ("line: %d\n", __LINE__);
  for (int i = 0; i < production_num; i++)
    printf ("%d -> %d %d\n", production[i].A, production[i].B, production[i].C);
  puts ("--------------------------------");
#endif

  // init the index which indexed by [production.B][production.C]
  for (int i = 0; i < production_num; i++)
  {
    int n1 = production[i].B;
    int n2 = production[i].C;
    if (p_idx[n1][n2].ptr == -1) p_idx[n1][n2].ptr = i;
    p_idx[n1][n2].size++;
  }

#ifdef __DEBUG__
  printf ("line: %d\n", __LINE__);
  for (int i = 0; i < production_num; i++)
  {
    for (int j = 0; j < production_num; j++)
      printf ("(%2d, %2d), ", p_idx[i][j].ptr, p_idx[i][j].size);
    puts ("");
  }
  puts ("--------------------------------");
#endif

  memset (tree, -1, sizeof (tree));
  // init tree_num's leaf-node by the number of times each vt
  for (int i = 0; i < string_length; i++)
  {
    int t = str[i];
    for (int j = i_idx[t].ptr; j < i_idx[t].ptr + i_idx[t].size; j++)
      tree[i][i][tree_num[i][i]++] = {item[j].A, 1};
  }

#ifdef __DEBUG__
  printf ("line: %d\n", __LINE__);
  for (int i = 0; i < string_length; i++)
  {
    for (int j = 0; j < string_length; j++)
      printf ("%d ", tree_num[i][j]);
    puts("");
  }
  puts ("--------------------------------");
#endif
#ifdef __DEBUG__
  for (int i = 0; i < string_length; i++)
  {
    for (int j = 0; j < string_length; j++)
    {
      for (int k = 0; k < 2; k++)
      {
        printf ("(%d,%d,%d) %2d,%2d ", i, j, k, tree[i][j][k].root, tree[i][j][k].num);
      }
      puts ("");
    }
    puts ("");
  }
  puts ("");
#endif

  Tree *l_tree = NULL, *r_tree = NULL;
  for (int len = 2; len <= string_length; len++)
  {
    for (int l = 0; l <= string_length - len; l++)
    {
      Tree buffer[2][STRING_MAX];
      int curr = 0, last = 1;
      int oldTreeNum = 0;
      
      for (int r = l + 1; r < l + len; r++)
      {
        for (int il = 0; il < tree_num[l][r - 1]; il++)
        {
          l_tree = &tree[l][r - 1][il];
          
          for (int ir = 0; ir < tree_num[r][l + len - 1]; ir++)
          {
            r_tree = &tree[r][l + len - 1][ir];
            int begin = p_idx[l_tree->root][r_tree->root].ptr;
            int end = begin + p_idx[l_tree->root][r_tree->root].size;

            if (begin == end) continue;
            swap(last, curr);
            int newTreeNum = 0;
            int k = 0;
            
            for (int p_idx = begin; p_idx < end; p_idx++)
            {
              Tree parent = {production[p_idx].A, l_tree->num * r_tree->num};
              
              while (k < oldTreeNum
                     && parent.root > buffer[last][k].root)
                buffer[curr][newTreeNum++] = buffer[last][k++];
              
              if (k < oldTreeNum
                  && parent.root == buffer[last][k].root)
                parent.num += buffer[last][k++].num;
              buffer[curr][newTreeNum++] = parent;
            }
            
            while (k < oldTreeNum)
              buffer[curr][newTreeNum++] = buffer[last][k++];
            
            oldTreeNum = newTreeNum;
          }
        }
        printf ("line: %d\n", __LINE__);
        int _i = 0;
        while (buffer[0][_i].root != -1)
        {
          printf ("%d %d\n", buffer[0][_i]);
        }
        puts ("--------------------------------");
        _i = 0;
        while (buffer[1][_i].root != -1)
        {
          printf ("%d %d\n", buffer[1][_i]);
        }
        puts ("--------------------------------");
      }

      tree_num[l][l + len - 1] = oldTreeNum;
      if (tree_num[l][l + len - 1] > 0)
      {
        memcpy(tree[l][l + len - 1], buffer[curr], tree_num[l][l + len - 1] * sizeof(Tree));
      }

#ifdef __DEBUG__
      printf ("line: %d, l: %d\n", __LINE__, l);
      for (int i = 0; i < string_length; i++)
      {
        for (int j = 0; j < string_length; j++)
          printf ("%d ", tree_num[i][j]);
        puts("");
      }
      puts ("--------------------------------");
#endif
    }
  }

#ifdef __DEBUG__
  for (int i = 0; i < string_length; i++)
  {
    for (int j = 0; j < string_length; j++)
    {
      printf("%d ", tree_num[i][j]);
    }
    puts("");
  }
#endif

  unsigned treeNum = 0;
  if (tree_num[0][string_length - 1] > 0)
  {
    if (tree[0][string_length - 1][0].root == 0)
    {
      treeNum = tree[0][string_length - 1][0].num;
    }
  }
  printf("%u\n", treeNum);
  return 0;
}
